package com.smh;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * @author shiminghui
 * @date 2025/2/6 18:37
 * @description: TODO
 */
public class _009_链表 {

    public ListNode reverseList(ListNode head) {
        ListNode tempNode = head;
        ArrayList<Integer> list = new ArrayList<>();
        while (tempNode != null) {
            list.add(0, tempNode.val);
            tempNode = tempNode.next;
        }

        tempNode = head;
        int i = 0;
        while (tempNode != null) {
            tempNode.val = list.get(i++);
            tempNode = tempNode.next;
        }
        return head;
    }

    // 创建一个新链表，然后遍历头插
    public ListNode reverseList1(ListNode head) {
        ListNode resNode = null;
        while (head != null) {
            resNode = new ListNode(head.val, resNode);
            head = head.next;
        }
        return resNode;
    }

    // 将原链表的第一个节点放到新链表的头
    public ListNode reverseList2(ListNode head) {
        ListNode resNode = null;
        while (head != null) {
            ListNode tempNode = head.next;
            head.next = resNode;
            resNode = head;
            head = tempNode;
        }
        return resNode;
    }

    // 遍历链表，将当前节点的next指向前一个节点
    public ListNode reverseList4(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode preNode = head;
        ListNode curNode = head.next;
        while (curNode != null) {
            ListNode tempNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = tempNode;
        }
        head.next = null;
        return preNode;
    }

    // 两个指针，一个代表新的链表，一个代表原链表，将原链表的第二个元素放到新链表的头
    public ListNode reverseList5(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head;
        ListNode oldHead = head;
        while (oldHead.next != null) {
            ListNode tempNode = oldHead.next.next;
            oldHead.next.next = newHead;
            newHead = oldHead.next;
            oldHead.next = tempNode;
        }
        return newHead;
    }

    //利用递归的方法
    // 利用递归遍历，在归来时将当前节点的next指向前一个节点
    public ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode tempNode = reverseList3(head.next);
        head.next.next = head;
        return tempNode;
    }

    @Test
    public void test01() {

    }

    // 使用

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


}
